Codeforces Round #86 (Div. 2)

A

弱智题,不断用 ll 除以 kk 即可。

#include <cstdio>

int k, l, cnt;

int main() {
    scanf("%d%d", &k, &l);
    while (l % k == 0) cnt++, l /= k;
    if (l == 1) printf("YES\n%d\n", cnt - 1);
    else puts("NO");
}

B

看到数据范围 n16n\le 16 考虑状压,直接暴力枚举子集判断是否有冲突即可。

时间复杂度 O(n22n)O(n^22^n)

Code

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 20;

string s[N], a, b;
int f[N][N], n, m, ans;

int find(string str) {
    int i = 0;
    while (str != s[i]) i++;
    return i;
}

int popcount(int x) {
    int ret = 0;
    while (x) ret += x & 1, x >>= 1;
    return ret;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i <= n - 1; i++) cin >> s[i];
    sort(s, s + n);
    for (int i = 1; i <= m; i++) {
        cin >> a >> b;
        int u = find(a), v = find(b);
        f[u][v] = f[v][u] = 1;
    }
    for (int s = 0; s <= (1 << n) - 1; s++) {
        int flag = 0;
        for (int i = 0; i <= n - 1; i++) {
            if ((s >> i & 1) == 0) 
                continue;
            for (int j = i + 1; j <= n - 1; j++) {
                if ((s >> j & 1) == 0) 
                    continue;
                flag |= f[i][j];
                if (flag) break;
            }
            if (flag) break;
        }
        if (flag == 0) {
            if (popcount(s) > popcount(ans))
                ans = s;
        }
    }
    cout << popcount(ans) << endl;
    for (int i = 0; i <= n - 1; i++) {
        if (ans >> i & 1)
            cout << s[i] << endl;
    }
}

C

大模拟,不知道为什么死活写不对。

搬一个题解代码。

Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;

const int N = 1e5 + 5;

char s[N], word[N];
int type[N], tp, p, flag, cnt, len, t;

int modify() {
    int l = strlen(word);
    if (l < 3) return 0;
    if (strcmp(word + l - 4, "lios") == 0) return 1;
    if (strcmp(word + l - 5, "liala") == 0) return -1;
    if (strcmp(word + l - 3, "etr") == 0) return 2;
    if (strcmp(word + l - 4, "etra") == 0) return -2;
    if (strcmp(word + l - 6, "initis") == 0) return 3;
    if (strcmp(word + l - 6, "inites") == 0) return -3;
    return 0;
}

int main() {
    cin.getline(s, N);
    flag = 1;
    len = strlen(s);
    for (int i = 0; i <= len; i++) {
        if (s[i] != ' ' && s[i] != '\0')
            word[p++] = s[i];
        else {
            word[p] = '\0';
            cnt++;
            t = modify();
            if (t != 0) type[tp++] = t;
            else {
                flag = 0;
                break;
            }
        }
    }
    if (cnt == 1 && flag == 1) {
        puts("YES");
        return 0;
    }
    if (flag == 0) {
        puts("NO");
        return 0;
    }
    cnt = 0;
    for (int i = 0; i < tp; i++) {
        if (abs(type[i]) == 2)
            cnt++;
    }
    if (cnt != 1) {
        puts("NO");
        return 0;
    }
    flag = 1;
    if (type[0] < 0) {
        for (int i = 1; i < tp; i++)
            if (type[i] > 0) {
                flag = 0;
                break;
            }
    }
    else {
        for (int i = 1; i < tp; i++)
            if (type[i] < 0) {
                flag = 0;
                break;
            }
    }
    if (flag == 0) {
        puts("NO");
        return 0;
    }
    flag = 1;
    for (int i = 1; i < tp; i++) {
        if (abs(type[i]) < abs(type[i - 1])) {
            flag = 0;
            break;
        }
    }
    if (flag) puts("YES");
    else puts("NO");
}
阅读全文 »

Codeforces Round #818 (Div. 2)

A

不妨设 ab,d=gcd(a,b)a\le b,\,d=\gcd(a,b)

a=da1,b=db1a=da_1,\,b=db_1 ,且 gcd(a1,b1)=1\gcd(a_1,b_1)=1

阅读全文 »